#include <stdlib.h>
#include <stdio.h>

typedef int ElemType;
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

//初始化双链表（带头结点）
bool InitDLinkList(DLinklist &L) {
    L = (DLinklist) malloc(sizeof(DNode));//分配一个头结点
    if (L == NULL) { //内存不足，分配失败
        return false;
    }
    L->prior = NULL;//头结点的prior永远指向NULL
    L->next = NULL;//头结点之后暂时还没有结点
    return true;
}

//判断双链表是否为空（带头结点）
bool Empty(DLinklist L) {
    if (L->next == NULL) return true;
    else return false;
}

//在p结点之前插入s结点
bool InsertNextDNode(DNode *p, DNode *s) {
    //谨记先后再前操作
    if (p == NULL || s == NULL) {//非法参数
        return false;
    }
    s->next = p->next;
    if (p->next != NULL) {//如果p结点有后继结点
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

//删除p结点的后继结点
bool DeleteNextNode(DNode *p) {
    if (p == NULL) return false;
    DNode *q = p->next;//找到p的后继结点
    if (q == NULL) return false;//p没有后继结点，就是最后一个结点
    p->next = q->next;
    if (q->next != NULL) //q结点不是最后一个结点
        q->next->prior = p;
    free(q);//释放结点空间
    return true;
}

//双链表的销毁
void DestroyList(DLinklist &L) {
    //循环释放各个数据结点
    while (L->next != NULL) {
        DeleteNextNode(L);
    }
    free(L);//释放头结点
    L = NULL;//头结点指向NULL
}

//后向遍历
void ForwardTraversalList(DLinklist L) {
    DLinklist p = L->next;
    while (p != NULL) {
        //对结点p做相应处理
        printf("%2d ", p->data);
        p = p->next;
    }
}

//前向遍历
void BackwardTraversalList(DLinklist L) {
    DLinklist p = L->next;
    while (p->next != NULL) {
        p = p->next;
    }
//    此时p到达链表尾
//如果当前链表的prior不为空
    if(p->prior==NULL) return ;
    while (p->prior != NULL) {
        //对结点p做相应处理
        printf("%2d ", p->data);
        p = p->prior;
    }
}

void textDLinkList() {
    //初始化双链表
    DLinklist L;
    InitDLinkList(L);
}

//双链表
int main() {
    textDLinkList();
    return 0;
}
